package com.multimedia.scala.euler

import scala.annotation.tailrec
/**
A permutation is an ordered arrangement of objects.
For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4.
If all of the permutations are listed numerically or alphabetically, we call it lexicographic order.
The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
 */
import com.multimedia.scala.TailRecTest
object Asd24 {
    def main(args : Array[String]) : Unit = {
        @tailrec
        def findPermutation(a: List[Int], n: Int, rez: List[Int] = List()): List[Int] = {
            if (a.size==2) {
                if (n==0) return (a.last::a.first::rez).reverse
                else return (a.first::a.last::rez).reverse
            }
            val nf = TailRecTest.factorialInt(a.size-1)
        	val num = (n/nf).toInt
        	println(num+":"+a+", "+rez)
        	return findPermutation(remove(a, num), n % nf, a(num)::rez)
        	//return a(num-1)
        }
        def remove (a: List[Int], i: Int): List[Int] = {
            if (a.size<2) return List()
            if (i==0) return a.drop(1)
            val (s, e) = a.splitAt(i+1)
            s.dropRight(1):::e
        }
        //a.permutations.foreach(println)
        //println(TailRecTest.factorial(10))
        var a = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
        println(findPermutation(a, 999999).map(x=>x.toString()).reduce(_+_))
        //println(remove(a, 5))
        //var a = List(0, 1, 2)
        //println(findPermutation(a, 5).map(x=>x.toString()).reduce(_+_))
        
    }
}
